package com.salim.leetcode.$53;

/**
 * Created by IntelliJ IDEA.
 * User: lvzc
 * Date: 2018/8/29
 * Time: 18:12
 */
public class MaximumSubarray {


    /**
     * leetcode答案1
     * @param nums
     * @return
     */
    public int maxSubArrayA1(int[] nums){
        if(nums == null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        int max = nums[0];
        //当前区间子数组最大值
        int temp = nums[0];
        for(int i = 1; i < nums.length; i ++) {
            max = Math.max(nums[i], max);
            //如果n不是负数
            if(temp + nums[i] >= temp) {
                temp += nums[i];
                //如果n-1是负数 子数组左边界移动到n
                if(nums[i] > temp) temp = nums[i];
            }
            else temp += nums[i];
            max = Math.max(temp, max);
        }
        return max;
    }

    /**
     * leetcode答案2
     * 动态规划 dp[n] = max(dp[n-1]+n,n)
     * res 遍历过程中出现过的最大子数组和
     * prev 记录n-1位下最优解
     * cur 记录n位下的最优解
     * @param nums
     * @return
     */
    public int maxSubArrayA2(int[] nums){
        int res = nums[0];
        int prev = nums[0];
        int cur = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], prev + nums[i]);
            prev = cur;
            res = Math.max(cur, res);
        }
        return res;
    }

    //自答
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }

        int maxSum = nums[0];
        //null表示没有计算过
        Integer nowSum = null;
        for(int i=0;i<nums.length;i++){
            maxSum = Math.max(maxSum,nums[i]);
            int tempSum = null==nowSum?nums[i]:nowSum+nums[i];
            if(nums[i]<0){
                //碰到负数 判断相加后是否大于0 如果不是 将该区间结束 开始下一个区间
                if(tempSum>=0){
                    nowSum = tempSum;
                }else{
                    //nowSum不为空说明有未刷新的最大和
                    if(nowSum!=null){
                        //刷新最大和
                        maxSum = Math.max(nowSum,maxSum);
                        //结束这个区间
                        nowSum = null;
                    }
                }
            }else{
                //刷新最大和 但不结束
                nowSum = tempSum;
                maxSum = Math.max(nowSum,maxSum);
            }
        }

        if(nowSum!=null){
            //刷新最大和 并结束
            return Math.max(nowSum,maxSum);
        }else{
            return maxSum;
        }
    }

    public static void main(String[] args) {
        MaximumSubarray maximumSubarray = new MaximumSubarray();
//        int[] a = {-2,1,-3,4,-1,2,1,-5,4};
//        System.out.println(maximumSubarray.maxSubArray(a));
//        int[] b = {3,-2,-3,-3,1,3,0};
//        System.out.println(maximumSubarray.maxSubArray(b));
//        int[] c = {1,2,-1,-2,2,1,-2,1};
//        //System.out.println(maximumSubarray.maxSubArray(c));
//        int[] d = {-2,1,-3,4,-1,2,1,-5,4};
//        //System.out.println(maximumSubarray.maxSubArray(d));
//        int[] e = {-1,-2};
//        //System.out.println(maximumSubarray.maxSubArray(e));
//        int[] f = {0,-3,1,1};
//        //System.out.println(maximumSubarray.maxSubArray(f));
//        int[] g = {9,0,-2,-2,-3,-4,0,1,-4,5,-8,7,-3,7,-6,-4,-7,-8};
//        System.out.println(maximumSubarray.maxSubArray(g));

    }
}
